
type Dim = Int
type Row = Int
type Col = Int
type Square = (Row,Col)
type Board = [Square]

attacks :: Square -> Square -> Bool
attacks (x1, y1) (x2, y2) = 
  x1 == x2 || y1 == y2 || abs(x1 - x2) == abs(y1 - y2)

legal1 :: Square -> Board -> Bool
legal1 sq sqs = all (not . attacks sq) sqs

legal :: Board -> Bool
legal [] = True
legal (sq:sqs) = legal1 sq sqs && legal sqs

findQueens :: Dim -> Board
findQueens d = findSoln d [] d d

findSoln :: Dim -> Board -> Row -> Col -> Board
findSoln _ b _ 0 = b
findSoln _ b 0 _ = []
findSoln d b r c = 
  let nextb = findSoln d b (r-1) c in
  if not $ legal1 (r,c) b then nextb else
  case findSoln d ((r,c):b) d (c-1) of
    [] -> nextb
    b  -> b

{- 
findQueens :: Dim -> Maybe Board
findQueens d = findSoln d [] d d

findSoln :: Dim -> Board -> Row -> Col -> Maybe Board
findSoln _ b _ 0 = Just b
findSoln _ _ 0 _ = Nothing
findSoln d b r c = 
  let nextb = findSoln d b (r-1) c in
  if not $ legal1 (r,c) b then nextb else
  case findSoln d ((r,c):b) d (c-1) of
    Just b -> Just b
    Nothing -> nextb

findAllQueens :: Dim -> [Board]
findAllQueens d = findAll d [] d d 

findAll :: Dim -> Board -> Row -> Col -> [Board]
findAll _ b r 0 = [b]
findAll _ _ 0 _ = []
findAll d b r c = 
  let nextb = findAll d b (r-1) c in
  if not $ legal1 (r,c) b then nextb else
  findAll d ((r,c):b) d (c-1) ++ nextb
-} 

